package com.dq.offer;

/**
 * @Author: Dang Qi
 * @Date: 2021/3/11  13:39
 * @Description:
 */
public class RegularMatch {
    public static void main(String[] args) {
        Solution solution = new RegularMatch().new Solution();
        String[] s = {"a","aa","aa", "aa", "aaa", "ab", "aab", "mississippi"};
        String[] p = {"ab*","b*", "a" ,"a*", "aa*a",".*", "c*a*b", "mis*is*p*."};
//        for(int i = 0; i < s.length; i++){
//            System.out.printf("s = %s\np = %s \nres = %s\n####################\n",s[i],p[i],solution.isMatch(s[i],p[i]));
////            break;
//        }

        System.out.println(solution.isMatch("a","aab*a"));
    }
    class Solution {
        public boolean isMatch(String s, String p) {
            return isMatchDP(s,p);
            //return isMatchRecursive(s, p);
        }
        public boolean isMatchDP(String s, String p) {
            int m = s.length(), n = p.length();
            boolean[][] dp = new boolean[m+1][n+1];

            for(int i = 0; i < m+1; i++) {
                for(int j = 0; j < n+1; j++){
                    if(j==0){
                        //空串
                        dp[i][j] = i==0;
                    }else{
                        if(p.charAt(j-1) != '*'){
                            if(i>0 && vaild(s.charAt(i-1), p.charAt(j-1))) dp[i][j] = dp[i-1][j-1];
                            else dp[i][j] = false;
                        }else{
                            //bukan
                            dp[i][j] = dp[i][j-2];
                            //kan
                            dp[i][j] |= (i-1>0 && vaild(s.charAt(i-1), p.charAt(j-2))) ? dp[i-1][j]:false;
                        }
                    }
                }
            }
            return isMatchRecursive(s, p);
        }
        //递归版
        public boolean isMatchRecursive(String s, String p) {
            //从后往前
            if(p.length()==0) return s.length()==0;
            int si = s.length()-1, pi = p.length()-1;

            switch (p.charAt(pi)){
                case '*':
                    //不要上一个
                    if(isMatchRecursive(s, p.substring(0,pi-1))) return true;
                        //要上一个
                    else if(si<0 || !vaild(s.charAt(si), p.charAt(pi-1))) return false;
                    return isMatchRecursive(s.substring(0, si), p);
                default:
                    if(si <0 || !vaild(s.charAt(si),p.charAt(pi))) return false;
                    return isMatchRecursive(s.substring(0,si), p.substring(0,pi));
            }
        }
        private boolean vaild(char s1, char p1){
            return s1=='.' || p1=='.' || p1 == s1;
        }
    }
}
